package com.yuanzhi.train.tree;

/**
 * 给定一个二叉树，找出其最小深度。
 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 说明：叶子节点是指没有子节点的节点。

 示例 1：
 输入：root = [3,9,20,null,null,15,7]
 输出：2

 示例 2：
 输入：root = [2,null,3,null,4,null,5,null,6]
 输出：5

 提示：
 树中节点数的范围在 [0, 105] 内
 -1000 <= Node.val <= 1000

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: yuanZhi...
 * @Date: created in  2022/1/22 10:27
 */
public class MinDepth {
    public static void main(String[] args) {
        System.out.println(minDepth(new TreeNode(1, null,
                new TreeNode(2, new TreeNode(3), null))));
        System.out.println(minDepth(new TreeNode(3, new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7)))));
        System.out.println(minDepth(new TreeNode(2, null, new TreeNode(3, null,
                new TreeNode(4, null, new TreeNode(5, null, new TreeNode(6)))))));
    }

    private static int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null){
            return minDepth(root.right) + 1;
        }
        if (root.right == null){
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}
